//
// Created by zuo on 2024/7/5.
// 题目链接 https://www.lanqiao.cn/problems/3226/learning/?page=1&first_category_id=1&problem_id=3226
//

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e5 + 9;
ll a[N], b[N];

int partition(ll a[], int l, int r)
{
    int pivot = a[r], i = l, j = r;
    while (i < j)
    {
        while (i < j && a[i] <= pivot) i++;
        while (i < j && a[j] >= pivot) j--;
        if (i < j) swap(a[i], a[j]);
        else swap(a[i], a[r]); // 必须交换 a[i] 和 a[r]
    }
    return i;
}

void QuickSort(ll a[], int l, int r)
{
    if (l < r)
    {
        int mid = partition(a, l, r);
        QuickSort(a, l, mid - 1);
        QuickSort(a, mid + 1, r);
    }
}

void MergeSort(ll a[], ll left, ll right)
{
    if (left == right) return; // 只有一个元素 返回

    int mid = (left + right) / 2; // 找到中间位置 向下取整
    MergeSort(a, left, mid);
    MergeSort(a, mid + 1, right);

    ll pl = left, pr = mid + 1, pb = left; // 注意 pb = right  而不是从0开始
    while (pl <= mid || pr <= right)
    {
        if (pl > mid) b[pb++] = a[pr++];
        else if (pr > right) b[pb++] = a[pl++];
        else
        {
            if (a[pl] < a[pr]) b[pb++] = a[pl++];
            else b[pb++] = a[pr++];
        }
    }
    // 记得最后 把辅助数组的内容 放到 原数组当中
    for (int i = left; i <= right; i++) a[i] = b[i];
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    ll n;
    cin >> n;
    for (ll i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    // 快速排序  nlogn 解决1e5问题规模 找一个pivot 左边都比它小 但是无序  右边都比它大 但是无序
    // QuickSort(a, 0, n - 1);

    // 归并排序  nlogn 解决1e5问题规模  找中间值mid 从小到大找  需要空间 O(n)
    MergeSort(a, 0, n - 1);

    for (int i = 0; i < n; i++) cout << a[i] << " \n"[i == n - 1];

    return 0;
}
